{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #回文子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code> ，请计算这个字符串中有多少个回文子字符串。</p>\n",
    "\n",
    "<p>具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;abc&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>三个回文子串: &quot;a&quot;, &quot;b&quot;, &quot;c&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s =<strong> </strong>&quot;aaa&quot;\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6个回文子串: &quot;a&quot;, &quot;a&quot;, &quot;a&quot;, &quot;aa&quot;, &quot;aa&quot;, &quot;aaa&quot;</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 70 题相同：<a href=\"https://leetcode-cn.com/problems/palindromic-substrings/\">https://leetcode-cn.com/problems/palindromic-substrings/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [a7VOhD](https://leetcode.cn/problems/a7VOhD/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [a7VOhD](https://leetcode.cn/problems/a7VOhD/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"', '\"aaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "               if s[i:j + 1] == s[i:j + 1][::-1]:\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i<0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for j in range(i+1):\n",
    "                temp = s[j:i+1]\n",
    "                # print(temp)\n",
    "                if temp == temp[::-1]:\n",
    "                    res+=1\n",
    "            return dfs(i-1)+res\n",
    "        n = len(s)\n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                res.append(s[i:j+1]==s[i:j+1][::-1])\n",
    "        return sum(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        if_aba = [[0] * (i+1) for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if_aba[i][i] = 1\n",
    "            if i-1 >= 0 and s[i] == s[i-1]:\n",
    "                if_aba[i][i-1] = 1\n",
    "        j = 2\n",
    "        while j < len(s):\n",
    "            for i in range(len(s)-j):\n",
    "                if_aba[i+j][i] = if_aba[i+j-1][i+1] if s[i]==s[i+j] else 0\n",
    "            j += 1\n",
    "        return sum([sum(if_aba[i]) for i in range(len(s))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        cnt = []\n",
    "        for i in range(len(s)):\n",
    "            cnt.append([0] * (i + 1))\n",
    "            cnt[i][i] = 1\n",
    "        for j in range(len(s)):\n",
    "            for i in range(j):\n",
    "                if s[i] == s[j]:\n",
    "                    if j == i + 1:\n",
    "                        cnt[j][i] = 1\n",
    "                    else:\n",
    "                        cnt[j][i] = cnt[j - 1][i + 1]\n",
    "                else:\n",
    "                    cnt[j][i] = 0\n",
    "        res = 0\n",
    "        for i in cnt:\n",
    "            for j in i:\n",
    "                res += j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        c,n = 0,len(s)\n",
    "        dp = [[0]*n for i in range(n)]\n",
    "        \n",
    "        for k in range(0, n):\n",
    "            for i in range(n-k):\n",
    "                start,end = i,i+k\n",
    "                if k==0:\n",
    "                    dp[start][end]=1\n",
    "                    c+=1\n",
    "                elif k==1:\n",
    "                    if s[i]==s[end]:\n",
    "                        dp[start][end]=1\n",
    "                        c+=1\n",
    "                else:\n",
    "                    if s[i] == s[end]:\n",
    "                        dp[start][end] = dp[start+1][end-1]\n",
    "                        if dp[start][end]==1:\n",
    "                            c+=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1 or dp[i + 1][j - 1]:\n",
    "                        res += 1\n",
    "                        dp[i][j] = True\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        count = 0\n",
    "        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            for j in range(0, len(s) - i):\n",
    "                #print(j, j + i)\n",
    "                if i == 0:\n",
    "                    dp[j][j + i] = 1\n",
    "                elif i == 1:\n",
    "                    dp[j][j + i] = int(s[j] == s[j + 1])\n",
    "                elif i >= 2:\n",
    "                    dp[j][j + i] = int(dp[j + 1][j + i - 1] and s[j] == s[j + i])\n",
    "                print(dp[j][j +i])\n",
    "                count += dp[j][j + i]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for i in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1:\n",
    "                        dp[i][j] = 1 \n",
    "                    elif dp[i+1][j-1]:\n",
    "                        dp[i][j] = dp[i+1][j-1] + 1\n",
    "                    if dp[i][j]:\n",
    "                        res += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        count=0\n",
    "        dp=[[0]*len(s)for i in range(len(s))]\n",
    "        for i in range(len(s),-1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if j==i :\n",
    "                        dp[i][j]=1\n",
    "                        # print(s[i:j+1])\n",
    "                        count+=1\n",
    "                        # print(count)\n",
    "                else:\n",
    "                    if s[i]==s[j]:\n",
    "                            if dp[i+1][j-1]>0:\n",
    "                                # print(s[i:j+1])\n",
    "                                dp[i][j]=dp[i+1][j-1]+1\n",
    "                                count+=1\n",
    "                                # print(count)\n",
    "                            elif (j-i)==1:\n",
    "                                # print(s[i:j+1])\n",
    "                                dp[i][j]=1\n",
    "                                count+=1\n",
    "                                # print(count)\n",
    "                        \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if s[i]!=s[j]:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if j - i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    elif j - i ==1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1]\n",
    "        print(dp)\n",
    "        return sum([sum(i) for i in dp])\n",
    "                        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        sons=[[0]*n for i in range(n)]\n",
    "        sub=[]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1):\n",
    "                if i==j:\n",
    "                    #print(1,i,j)\n",
    "                    sons[i][j]=1\n",
    "                    #print(sons)\n",
    "                    sub.append(s[i])\n",
    "                else:\n",
    "                    if s[i]==s[j]:\n",
    "                        if i-j<2:\n",
    "                            #print(2,i,j)\n",
    "                            sons[i][j]=1\n",
    "                            #print(sons)\n",
    "                            sub.append(s[j:i+1])\n",
    "                        else:\n",
    "                            #print(3,i,j)\n",
    "                            sons[i][j]=sons[i-1][j+1]\n",
    "                            #print(sons)\n",
    "\n",
    "        print(sub,sons)\n",
    "        return sum(sum(x) for x in sons)\n",
    "\n",
    "\n",
    "                            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        \n",
    "        sum = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 1\n",
    "            sum += 1\n",
    "        \n",
    "        for i in range(1,len(s)):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if s[i] == s[j]:\n",
    "                    if i - j > 1:\n",
    "                        dp[j][i] = dp[j+1][i-1]\n",
    "                    else:\n",
    "                        dp[j][i] = 1\n",
    "                    if dp[j][i] == 1:\n",
    "                        sum +=1\n",
    "        \n",
    "        print(dp)\n",
    "\n",
    "        return sum\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n, ans = len(s), 0\n",
    "        h = [[None] * n for _ in range(n)]\n",
    "\n",
    "        def dep(x, y):\n",
    "            nonlocal h, ans\n",
    "            if h[x][y] is not None:\n",
    "                return\n",
    "            if x == y:\n",
    "                h[x][y] = True\n",
    "            elif y - x == 1:\n",
    "                h[x][y] = (s[x] == s[y])\n",
    "            else:\n",
    "                dep(x + 1, y - 1)\n",
    "                h[x][y] = (h[x + 1][y - 1] and s[x] == s[y])\n",
    "            ans += 1 if h[x][y] else 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                dep(i, j)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        # i~j是否是回文串(d[i][j])\n",
    "        # 1. s[i] == s[j]? \n",
    "        #   1.1 i跟j是否相等; 1.2 s[i]与s[j]是否相等\n",
    "        # 2. d[i+1][j-1]是否是回文串\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        d = [[-1 for i in range(len(s))] for j in range(len(s))]\n",
    "        def check_palindrome(low, high):\n",
    "            if low == high or (high == low+1 and s[high] == s[low]):\n",
    "                return 1\n",
    "            if s[low] == s[high]:\n",
    "                if d[low+1][high-1] == -1:\n",
    "                    d[low+1][high-1] = check_palindrome(low+1, high-1)\n",
    "                return d[low+1][high-1]\n",
    "            return 0\n",
    "        # print(d)\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                if d[i][j] == -1:\n",
    "                    d[i][j] = check_palindrome(i, j)\n",
    "                res += d[i][j]\n",
    "        # print(d)\n",
    "        # res = sum(sum(i) for i in d)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n, ans = len(s), 0\n",
    "        substr_map = [[0 for _ in range(n)] for __ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if i == j: # 单独字符必定是回文串\n",
    "                    substr_map[i][j] = 1\n",
    "                elif i == j-1: # 相邻字符若相同则是回文串\n",
    "                    substr_map[i][j] = 1 if s[i] == s[j] else 0\n",
    "                else: # 其余情况，只与两端字符相等，且中间是回文串有关\n",
    "                    substr_map[i][j] = substr_map[i+1][j-1] and s[i] == s[j] \n",
    "            ans += sum(substr_map[i])\n",
    "        print(substr_map)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)] # dp[i][j]表示字符串s[i:j+1]是否为回文字符串\n",
    "        for i in range(n):\n",
    "            for j in range(i, -1, -1):\n",
    "                if s[i]==s[j]:\n",
    "                    if i-j<=1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j+1]\n",
    "        print(dp)\n",
    "        return sum([dp[i][j] for i in range(n) for j in range(n)])\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i] = True\n",
    "\n",
    "        for L in range(2, n+1):\n",
    "            for i in range(n-L+1):\n",
    "                j = i + L - 1\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = False\n",
    "                else:\n",
    "                    if j - i > 1:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = True\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if dp[i][j]:\n",
    "                    ans += 1\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        print(dp)\n",
    "        ans = 0\n",
    "        i = n - 1\n",
    "        while i >= 0:\n",
    "            j = i\n",
    "            while j < n:\n",
    "                if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):\n",
    "                    ans += 1\n",
    "                    dp[i][j] = True\n",
    "                j += 1\n",
    "            i -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        arr = np.zeros((n, n))\n",
    "        for i in range(n):\n",
    "            arr[i,i] = 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if (s[i] == s[j] and (j - i <= 1 or arr[i + 1][j - 1])):\n",
    "                    arr[i][j] = 1;\n",
    "                    \n",
    "        return int(arr.sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = np.zeros((n,n))\n",
    "        for i in range(n):\n",
    "            row = n-i-1\n",
    "            for j in range(row,n):\n",
    "                if j == row:\n",
    "                    dp[row][j] = 1\n",
    "                elif j-row == 1 and s[j] == s[row]:\n",
    "                    dp[row][j] = 1\n",
    "                elif j-row > 1 and dp[row+1][j-1] == 1 and s[j] == s[row]:\n",
    "                    dp[row][j] = 1\n",
    "            \n",
    "        return int(np.sum(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[False for _ in range(n)]for _ in range(n)]\n",
    "        res=0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i,n):\n",
    "                if s[i]==s[j] and (j-i<=1 or dp[i+1][j-1]):\n",
    "                    dp[i][j]=True\n",
    "                    res+=1\n",
    "        print(dp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False]*n for _ in range(n)]\n",
    "        cnt = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = True\n",
    "            for j in range(i, n):\n",
    "                if j==i+1:\n",
    "                    dp[i][j] = s[i]==s[j]\n",
    "                if j>i+1:\n",
    "                    dp[i][j] = dp[i+1][j-1] and s[i]==s[j]\n",
    "\n",
    "                if dp[i][j]:\n",
    "                    cnt += 1\n",
    "        print(dp)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        size = len(s)\n",
    "        dp = [[False]*(size+1) for i in range(size+1)]\n",
    "        count=0\n",
    "        for i in range(size,0,-1):\n",
    "            for j in range(i,size+1):\n",
    "                if s[i-1]==s[j-1]:\n",
    "                    if j-i<=1:\n",
    "                        dp[i][j]=True\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                    count+=1 if dp[i][j]==True else 0\n",
    "                        \n",
    "        print(dp)\n",
    "        return count\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        # 二维动态规划，dp[i][j]表示从第i个字符到第j个字符构成几个子串\n",
    "        # 字符串[i, j]闭区间\n",
    "        # 最终结果是dp[0, len(s) - 1]\n",
    "        # 使用record[i][j]表示从i到j【i，j】闭区间是否回文。\n",
    "        n  = len(s)\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]\n",
    "        record = [[0 for i in range(n)] for j in range(n)] # 记录从i到j 是否是回文\n",
    "\n",
    "        for size in range(n):\n",
    "            for i in range(n - size):\n",
    "                if size == 0:\n",
    "                    dp[i][i + size] = 1\n",
    "                    record[i][i + size] = 1\n",
    "                elif size == 1:\n",
    "                    if s[i] == s[i + 1]:\n",
    "                        dp[i][i + size] = 3\n",
    "                        record[i][i + size] = 1\n",
    "                    else:\n",
    "                        dp[i][i + size] = 2\n",
    "                        record[i][i + size] = 0\n",
    "                else:\n",
    "                    dp[i][i + size] = dp[i][i + size - 1] + dp[i + 1][i + size] - dp[i + 1][i + size - 1]  \n",
    "                    if s[i] == s[i + size] and record[i + 1][i + size - 1] == 1:\n",
    "                        dp[i][i + size] += 1\n",
    "                        record[i][i + size] = 1\n",
    "        return dp[0][n - 1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[0]*len(s) for _ in range(len(s))]\n",
    "        for _ in range(len(s)):\n",
    "            dp[_][_] = 1\n",
    "        \n",
    "        for j in range(len(s)):\n",
    "            for i in range(j):\n",
    "                if s[i] == s[j] and (j-i<2 or dp[i+1][j-1]==1):\n",
    "                    dp[i][j] = 1\n",
    "        \n",
    "        return sum(sum(dp,[]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        import numpy\n",
    "        ma=[[0 for i in range(len(s))] for i in range(len(s))]\n",
    "        for c in range(len(s)):\n",
    "            for j in range(len(s)-c):\n",
    "                jj=j+c\n",
    "                if j==jj:\n",
    "                    ma[j][jj]=1\n",
    "                elif j+1==jj:\n",
    "                    if s[j]==s[jj]:\n",
    "                        ma[j][jj]=1\n",
    "                else:\n",
    "                    if s[j]==s[jj]:\n",
    "                        ma[j][jj]=ma[j+1][jj-1]\n",
    "        su= numpy.sum(ma)\n",
    "        return int(su)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        def findstr(arr,left,right):\n",
    "            tmp = [] #保存中间结果，防止漏记，如a，aaa\n",
    "            while left>=0 and right<len(arr) and arr[left]==arr[right]:\n",
    "                tmp.append(arr[left] + arr[right])  \n",
    "                left -= 1\n",
    "                right += 1 \n",
    "            return tmp\n",
    "        final_res = []\n",
    "        for i in range(len(s)*2-1):\n",
    "            res = findstr(s, i//2, i//2+i%2)\n",
    "            #e_res = findstr(s, i, i+1)\n",
    "            for i in res:\n",
    "                final_res.append(i)\n",
    "        return len(final_res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        def findstr(arr,left,right):\n",
    "            tmp = [] #保存中间结果，防止漏记，如a，aaa\n",
    "            while left>=0 and right<len(arr) and arr[left]==arr[right]:\n",
    "                tmp.append(arr[left] + arr[right])  \n",
    "                left -= 1\n",
    "                right += 1 \n",
    "            return tmp\n",
    "        final_res = []\n",
    "        for i in range(len(s)*2-1):\n",
    "            res = findstr(s, i//2, i//2+i%2)\n",
    "            #e_res = findstr(s, i, i+1)\n",
    "            for i in res:\n",
    "                final_res.append(i)\n",
    "        print(final_res)\n",
    "        return len(final_res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        p = dict() # 判断ij是否回文\n",
    "        c2loc = dict() # 字符位置\n",
    "        ret = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c not in c2loc:\n",
    "                c2loc[c] = [i]\n",
    "                ret += 1\n",
    "                p[i * 1000 + i] = True\n",
    "            else:\n",
    "                c2loc[c].append(i)\n",
    "                for j in c2loc[c]:\n",
    "                    idx = (j+1) * 1000 + i - 1\n",
    "                    if i-j <= 1 or idx in p:\n",
    "                        ret += 1\n",
    "                        p[j * 1000 + i] = True\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        def is_huiwen(s):\n",
    "            left = 0\n",
    "            right = len(s) - 1\n",
    "            while left < right:\n",
    "                if s[left] != s[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "\n",
    "        length = len(s)\n",
    "        total = 0\n",
    "        hash = {}\n",
    "        for i in range(length):\n",
    "            for j in range(0, i+1):\n",
    "                if s[i] == s[j] and (i - 1 <= j + 1 or hash.get(\"{}_{}\".format(j+1, i-1), 0)):\n",
    "                    total += 1\n",
    "                    hash[\"{}_{}\".format(j, i)] = 1\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        record = {}\n",
    "        def palindrome(s):\n",
    "            if s in record:\n",
    "                return record[s]\n",
    "            if len(s) == 0:\n",
    "                return True            \n",
    "            if s[0] != s[-1]:\n",
    "                return False\n",
    "            record[s] = palindrome(s[1:-1])\n",
    "            return record[s]\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i, len(s)):\n",
    "                if palindrome(s[i:j+1]):\n",
    "                    count+=1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        is_pa = set()\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1):\n",
    "                if s[i]==s[j]:\n",
    "                    if i-j<=2 or (j+1,i-1) in is_pa:\n",
    "                        is_pa.add((j,i))\n",
    "                        count = count +1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = n\n",
    "        def ishuiwen(s):\n",
    "            if s[::-1]==s:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        ans=0\n",
    "        set_s = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i,n+1):\n",
    "                s_s = s[i:j]\n",
    "                if ishuiwen(s_s) and (i,j) not in set_s and i!=j:\n",
    "                    set_s.add((i,j))\n",
    "                   \n",
    "                    ans+=1\n",
    "        # print(set_s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        def isstring(l,r):\n",
    "            while l>=0 and r<n:\n",
    "                if s[l] == s[r]:\n",
    "                    path.append([l,r])\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        n = len(s)\n",
    "        num = 0\n",
    "        path = []\n",
    "        for l in range(n):\n",
    "            isstring(l,l)\n",
    "            if l+1 < n:\n",
    "                isstring(l,l+1)\n",
    "        \n",
    "        return len(path)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dq = deque()\n",
    "        seen = set()\n",
    "        for i in range(n):\n",
    "            dq.append((i, i))\n",
    "            seen.add((i, i))\n",
    "        for i in range(n - 1):\n",
    "            if s[i] == s[i + 1]:\n",
    "                dq.append((i, i + 1))\n",
    "                seen.add((i, i + 1))\n",
    "        \n",
    "        count = 0\n",
    "        while dq:\n",
    "            x, y = dq.popleft()\n",
    "            count += 1\n",
    "            if 0 <= x - 1 < n and 0 <= y + 1 < n:\n",
    "                if s[x - 1] == s[y + 1]:\n",
    "                    dq.append((x - 1, y + 1))\n",
    "                    seen.add((x - 1, y + 1))\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        visit = set()\n",
    "        \n",
    "        def dfs(start, end):\n",
    "            if (start, end) in visit:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if start>end:\n",
    "                return True\n",
    "            if s[start]==s[end]:\n",
    "                if end-start+1<3:\n",
    "                    if (start, end) not in visit:\n",
    "                        visit.add((start, end))\n",
    "                        ans += 1\n",
    "                    return True \n",
    "                else:\n",
    "                    if dfs(start+1,end-1):\n",
    "                        visit.add((start, end))\n",
    "                        ans += 1\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        for i in range(0,n-1):\n",
    "            for j in range(i,n):\n",
    "                dfs(i,j)\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        flag_matrix = [ [0]*len(s) for i in range(len(s)) ]\n",
    "        res_list = []\n",
    "        for i in range(len(s)):\n",
    "            flag_matrix[i][i] = 1\n",
    "            res_list.append([i, i])\n",
    "        for i in range(1, len(s)):\n",
    "            if i != 1:\n",
    "                for j in range(0, len(s)-i):\n",
    "                    if flag_matrix[j+1][j+i-1] == 1:\n",
    "                        if s[j] == s[j+i]:\n",
    "                            flag_matrix[j][j+i] = 1\n",
    "                            res_list.append([j, j+i])\n",
    "            else:\n",
    "                for j in range(0, len(s)-i):\n",
    "                    if s[j] == s[j+1]:\n",
    "                        flag_matrix[j][j+1] = 1\n",
    "                        res_list.append([j, j+1])\n",
    "        return len(res_list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        # def judge(s1):\n",
    "        #     m=len(s1)\n",
    "        #     start,end=0,m-1\n",
    "        #     while start<end:\n",
    "        #         if s1[start]!=s1[end]:\n",
    "        #             return False\n",
    "        #     return True\n",
    "        judge_dict=collections.defaultdict(int)\n",
    "        n=len(s)\n",
    "        s_len=[0]*(n+1)\n",
    "        s_len[1]=n\n",
    "        for i in range(n):\n",
    "            judge_dict[(i,i)]=1\n",
    "            if i<n-1:\n",
    "                judge_dict[(i+1,i)]=1\n",
    "        for i in range(2,n+1):\n",
    "            start=0\n",
    "            end=i-1\n",
    "            while end<n:\n",
    "                if s[start]==s[end] and judge_dict[(start+1,end-1)]==1:\n",
    "                    s_len[i]+=1\n",
    "                    judge_dict[(start,end)]=1\n",
    "                start+=1\n",
    "                end+=1\n",
    "        return sum(s_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "    \n",
    "        dp =  [ [False] * (1 + n) for _ in range(1 + n)]\n",
    "        ans = set()\n",
    "        for L in range(1, 1 + n):\n",
    "            for i in range(n):\n",
    "                j = L + i -1\n",
    "                if j < n:\n",
    "                    if s[i] == s[j]:\n",
    "                        if j - i + 1 <= 3:\n",
    "                            dp[i][j] = True\n",
    "                        else:\n",
    "                            dp[i][j] = dp[i+1][j-1]\n",
    "                        if dp[i][j]:\n",
    "                            ans.add((i, j))\n",
    "        return len(ans)\n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for i in range(len(s)):\n",
    "            m1[(i,i)] =True\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(0, i):\n",
    "                if s[j] == s[i]:\n",
    "                    if j+1 ==i:\n",
    "                        m1[(j,i)] = True\n",
    "                    else:\n",
    "                        if m1[ (j+1,i-1) ] is True:\n",
    "                            m1[(j,i)] = True\n",
    "                        else:\n",
    "                            m1[(j,i)] = False\n",
    "                else:\n",
    "                    m1[(j,i)] = False\n",
    "        cnt = 0\n",
    "        for i in m1:\n",
    "            if m1[i] is True:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def check(i,j):\n",
    "            while i<j:\n",
    "                if s[i]!=s[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return True\n",
    "        \n",
    "\n",
    "        res=0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                if check(i,j):\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        lens = len(s)\n",
    "\n",
    "        dp = [[[False] for _ in range(lens)] for _ in range(lens)]\n",
    "\n",
    "        for i in range(lens):\n",
    "            dp[i][i] = True\n",
    "        res = lens\n",
    "        for i in range(lens-1,-1,-1):\n",
    "            for j in range(i+1,lens):\n",
    "                print(s[i],s[j],s[i] == s[j])\n",
    "                if s[i] == s[j]:\n",
    "                    if i + 1 == j:\n",
    "                        dp[i][j] = True\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        if dp[i+1][j-1] == True:\n",
    "                            dp[i][j] = True\n",
    "                            res += 1\n",
    "        return res\n",
    "# class Solution:\n",
    "#     def countSubstrings(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "\n",
    "#         dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "#         for i in range(n):\n",
    "#             dp[i][i] = True\n",
    "        \n",
    "#         res = n\n",
    "#         for l in range(n-1, -1, -1):\n",
    "#             for r in range(l + 1, n):\n",
    "#                 if s[l] == s[r]:\n",
    "#                     if r - l == 1:\n",
    "#                         dp[l][r] = True\n",
    "#                         res += 1    \n",
    "#                     else:\n",
    "#                         if dp[l+1][r-1] == True:\n",
    "#                             dp[l][r] = True\n",
    "#                             res += 1\n",
    "#         return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
